#define _CRT_SECURE_NO_WARNINGS 1
#include"BinarySearchTree.h"
#include<string>

void test1()
{
	BSTree<int> t;
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	for (auto e : a)
	{
		t.Insert(e);
	}

	t.InOrder();

	t.Erase(4);
	t.InOrder();

	t.Erase(6);
	t.InOrder();

	t.Erase(7);
	t.InOrder();

	t.Erase(3);
	t.InOrder();

	cout << t.Find(3) << " " << t.Find(8) << endl;

	for (auto x : a)
	{
		t.Erase(x);
	}
	t.InOrder();

}

void test2()
{
	BSTree<int> t;
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	for (auto e : a)
	{
		t.InsertR(e);
	}

	t.InOrder();

	t.EraseR(4);
	t.InOrder();

	t.EraseR(6);
	t.InOrder();

	t.EraseR(7);
	t.InOrder();

	t.EraseR(3);
	t.InOrder();

	cout << t.FindR(3) << " " << t.FindR(8) << endl;

	for (auto x : a)
	{
		t.EraseR(x);
	}
	t.InOrder();

}

void test3()
{
	BSTree<int> t;
	int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	for (auto e : a)
	{
		t.InsertR(e);
	}
	t.InOrder();

	BSTree<int> t1(t);
	t1.InOrder();

	BSTree<int> t2;
	t2 = t;
	t2.InOrder();

}

//查找单词
void test4()
{
	key_value::BSTree<string, string> dict;

	dict.InsertR("insert", "插入");
	dict.InsertR("modify", "修改");
	dict.InsertR("erase", "删除");
	dict.InsertR("find", "查找");

	string in;
	while (cin >> in)
	{
		if (dict.FindR(in) == nullptr)
		{
			cout << "无此单词" << endl;
		}
		else
		{
			cout << dict.FindR(in)->_value << endl;
		}
	}
}

//统计水果的个数
void test5()
{
	string arr[] = { "苹果","西瓜","桃子","哈密瓜","哈密瓜", "哈密瓜", "哈密瓜", "哈密瓜","西瓜","桃子" ,"西瓜","桃子" };
	key_value::BSTree<string, int> fruittree;
	for (auto& str : arr)
	{
		if (fruittree.FindR(str) == nullptr)
		{
			fruittree.InsertR(str, 1);
		}
		else
		{
			fruittree.FindR(str)->_value++;
		}
	}
	fruittree.InOrder();
}

int main()
{
	test1();
	cout << "---------------------------------" << endl;

	test2();
	cout << "---------------------------------" << endl;

	test3();
	cout << "---------------------------------" << endl;

	//test4();
	//cout << "---------------------------------" << endl;

	test5();

	return 0;
}